/**
 * 516. 最长回文子序列
 *
 * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。
 * 可以假设 s 的最大长度为 1000 。
 *
 *     区间规划问题
 *
 * 动态转移方程：
 *  dp[i][j] 表示从下标i到下标j的最长回文长度
 *  1)、首尾两个字符相等时
 *      dp[i][j] = 2 + (len == 2 ? 0:dp[i+1][j-1])
 *  2)、首尾两个字符不相同时
 *      dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
 */

public class Solution_516 {
    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int dp[][] = new int[n][n];

        //初始化
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        //dp字符串从2开始
        for (int len = 2; len <= n; len++) {
            //i j表示当前字符串的起始下标和结束下标
            for (int i = 0;i < n - len + 1; i++) {
                int j = i + len - 1;

                if (chars[i] == chars[j]) {
                    dp[i][j] = 2 + (len == 2 ? 0 : dp[i+1][j-1]);
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];
    }
}
